Spanning Tree Protocols (STPs) are used in computer networks to maintain a reconfigurable on-failure loop-free network topology within a group of interconnected switches having redundant paths. In the original STP specification (IEEE 802.ID, published by the Institute of Electrical and Electronic Engineers), failover and failback of links to employ alternate paths was timer-based.
Enhancements to the core spanning tree protocol were suggested, allowing rapid convergence and recovery of the spanning tree after link failure, independent of any timer. These enhancements became known as the Rapid Spanning Tree Protocol (RSTP), described in the IEEE 802.1 w specification, currently merged into the IEEE 802.1D-2004 standard.
Further enhancements to the basic spanning tree protocol were made to allow a group of switches to run multiple spanning trees instances within the same spanning tree domain. In such an enhanced protocol, an administrator provisions each switch in the spanning tree domain with a mapping between spanning tree instances and VLANs (Virtual Local Area Networks), and tailors the bridge parameters in each switch so that different multiple spanning tree instances will converge to different least cost paths through the network. The traffic for each VLAN is forwarded along the network paths for the spanning tree instance mapped to that VLAN. With some effort, an administrator can therefore achieve better load balancing than is generally possible with a single spanning tree instance, since no operational port will necessarily be blocked in all spanning tree instances. These enhancements are described in the IEEE 802.1s standard as the “Multiple Spanning Tree Protocol” (MSTP). Currently, MSTP has been integrated into the IEEE 802.1Q-2003 standard.
Additional enhancements in the field of spanning tree design are described in U.S. patent application Ser. No. 11/065,724, entitled “Packet Attribute-Mapped Spanning Tree Protocol,” filed Feb. 24, 2005, and incorporated herein by reference. The Attribute-Mapped Spanning Tree Protocol (AMSTP) can be configured to map packet attributes other than (or in addition to) VLAN identifier to logical spanning tree instances. For instance, different spanning trees can be associated with different Ethernet layer 2 header Ethertypes, layer 3 addresses or portions of addresses, layer 4 types indicated by layer 3, IP options, multicast/unicast traffic, higher-layer header attributes, data attributes for specific packet types, etc. This structure provides powerful flexibility for dividing network resources according to a wide variety of specific traffic attributes.
All of these topology management solutions can be considered as spanning tree protocols and will be referred to herein as “STP” wherever the particular distinctions between these protocols are not pertinent to the discussion.
In laboratory tests, the time necessary for MSTP to converge to a new topology upon failure ranges from milliseconds to seconds, depending on the location of the failure in the network. Such a large variation in convergence time presents a challenge to network designers evaluating network failure scenarios and designing a network that meets connectivity guarantees for time-sensitive applications (Voice over Internet Protocol (VoIP), Digital Video-on-Demand, etc.) A spanning tree protocol that provides extremely fast and consistent failover performance could provide significant advantages over RSTP-like failover mechanisms.
Another type of topology management protocol that has been used in some specialized network topologies is a ring protocol. Ring protocols can be defined on a set of network nodes that are linked in a loop, such as the transport nodes in a large Metropolitan Area Network (MAN). Typically, a ring protocol is provisioned and enabled on the ring nodes manually, and one port on one node is designated as blocking to prevent network traffic from looping on the ring. The ring nodes circulate a control plane Protocol Data Unit (PDU) that contains a health check token. The PDUs can circulate on the ring as fast as the sum of the times it takes the nodes to receive, consume, process, and resend the PDUs for a given token, generally on the order of milliseconds for a ring. Should a health check PDU go missing, a timer expires on the node having the designated blocking port, and all nodes in the ring are instructed to flush and relearn their forwarding tables. Thus failure detection and recovery time is generally fast and predictable, with little dependence on the point of ring failure.
Current ring protocols are not without disadvantages. Such protocols enforce topological restrictions that limit applicability to only certain network configurations. Many such protocols are vendor-specific, and thus can only operate when all nodes in a ring were supplied by the vendor. The IEEE has now promulgated the IEEE 802.17 standard for “Resilient Packet Rings” (RPR) in fiber ring topologies. The RPR provides a MAC layer protocol specifically for Metro ring networks. The protocol makes some assumptions regarding the ring-like topology that are not consistent or compatible with the generic Ethernet MAC layer. Thus RPR, like the other ring protocols, requires topological constraints and lacks interoperability with currently deployed infrastructures.